__author__ = 'st316'
'''
Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
'''


class Solution:
    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRange(self, A, target):
        start = 0
        end = len(A) - 1
        flag = False
        mid = 0
        while start <= end:
            mid = (start + end) / 2
            if A[mid] == target:
                flag = True
                break
            elif A[mid] > target:
                end = mid - 1
            else:
                start = mid + 1

        if flag:
            s, e = mid, mid
            while s > -1 and A[s] == target:
                s -= 1
            while e < len(A) and A[e] == target:
                e += 1
            return [s + 1, e - 1]
        return [-1, -1]

    # @param A, a list of integers
    # @param target, an integer to be searched
    # @return a list of length 2, [index1, index2]
    def searchRangeX(self, A, target):
        r = [-1, -1]
        n = len(A)
        lower = 0
        upper = n

        # Search for lower bound
        while lower < upper:
            mid = (lower + upper) / 2
            if A[mid] < target:
                lower = mid + 1
            else:
                upper = mid

        # If the target is not found, return (-1, -1)
        if lower > n - 1 or A[lower] != target:
            return r
        r[0] = lower

        # Search for upper bound
        upper = n
        while lower < upper:
            mid = (lower + upper) / 2
            if A[mid] > target:
                upper = mid
            else:
                lower = mid + 1
        r[1] = upper - 1

        return r


if __name__ == '__main__':
    s = Solution()
    print s.searchRangeX([3, 4, 4, 4, 5], 4)